public class HashBucKet {
    static class Node{
        public int key;
        public Node next;
        public int val;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    //定义一个usedsize计数容量
    public int usedsize = 0;
    //构造一个数组加链表的哈希桶
    public Node[] elem;
    //定义负载因子，根据负载因子来减少冲突
    public static final double LOAD_FACTOR = 0.75;
    //构造方法初始化哈希桶
    public HashBucKet() {
        this.elem = new Node[10];
    }

    //在哈希桶里面插入数据
    public void put(int key,int val){
        int index = key % elem.length;
        Node cur = elem[index];
        while (cur != null){
            if(cur.key == key){
                cur.val = val;
            }
            cur = cur.next;
        }
        //采用头插法来插入数据
        Node node = new Node(key,val);
        node.next = elem[index];
        elem[index] = node;
        usedsize++;
        //在插入数据的时候要根据负载因子来对数组进行扩容，尽量避免哈希冲突
        if(calculatorLoadFactor() >= LOAD_FACTOR){
            //对
            recapacity();
        }
    }
    //对数组进行扩容
    private void recapacity() {
        //二倍扩容
        //扩容之后，每个数据要进行新的哈希计算，在新的数组长度中寻找到对应的位置
        Node[] newelem = new Node[elem.length*2];
        for (int i = 0; i < elem.length; i++) {
            Node cur = elem[i];
            while (cur != null){
                Node curNext = cur.next;
                //对旧数组里面的数据重新计算在新数组里面的哈希地址
                int index = cur.key % newelem.length;
                //在新数组中进行头插
                cur.next = newelem[index];
                newelem[index] = cur;
                cur = curNext;
            }
        }
        elem = newelem;
    }
    //在哈希表中查找某个数据并返回
    public int get(int key){
        int index = key % elem.length;
        Node cur = elem[index];
        while (cur != null){
            if (cur.key == key){
                return  cur.key;
            }
            cur = cur.next;
        }
        return -1;
    }

    //计算哈希桶的负载因子,根据负载因子大小来对数据进行扩容,尽量避免哈希冲突
    private double calculatorLoadFactor(){
        return usedsize*1.0/elem.length;
    }
}
